Combination

In combinatorial mathematics, a k-combination of a finite set S is a subset of k distinct elements of S. Specifying a subset does not arrange them in a particular order; by contrast, producing the k distinct elements in a specific order defines a sequence without repetition, also called k-permutation (but which is not a permutation of S in the usual sense of that term). As an example, a poker hand can be described as a 5-combination of cards from a 52-card deck: the 5 cards of the hand are all distinct, and the order of the cards in the hand does not matter.

The number of k-combinations of an n-element set is equal to the binomial coefficient $\tbinom nk$ . For this reason the set of all k-combinations of a set X is sometimes denoted by $\tbinom Xk$ .

1 Number of k-combinations
- 1.1 Example of counting combinations
2 Number of combinations with repetition
- 2.1 Example of counting multicombinations
3 See also
4 References
5 External links

Number of k-combinations

Main article: Binomial coefficient

The number of k-combinations from a given set S of n elements is often denoted in elementary combinatorics texts by C(n,k), or by a variation such as $C^n_k$ , ${}_nC_k$ , ${}^nC_k$ or even $C_n^k$ (the latter form is standard in French and Polish texts). The same number however occurs in many other mathematical contexts, where it is denoted by $\tbinom nk$ ; notably it occurs as coefficient in the binomial formula, hence its name binomial coefficient. One can define $\tbinom nk$ for all natural numbers k at once by the relation

$\textstyle(1+X)^n=\sum_{k\geq0}\binom nk X^k,$

from which it is clear that $\tbinom n0=\tbinom nn=1$ and $\tbinom nk=0$ for k > n. To see that these coefficients count k-combinations from S, one can first consider a collection of n distinct variables X_s labeled by the elements s of S, and expand the product over all elements of S:

$\textstyle\prod_{s\in S}(1+X_s);$

it has 2ⁿ distinct terms corresponding to all the subsets of S, each subset giving the product of the corresponding variables X_s. Now setting all of the X_s equal to the unlabeled variable X, so that the product becomes (1 + X)ⁿ, the term for each k-combination from S becomes X^k, so that that the coefficient of that power in the result equals the number of such k-combinations.

Binomial coefficients can be computed explicitly in various ways. To get all of them for the expansions up to (1 + X)ⁿ, one can use (in addition to the basic cases already given) the recursion relation

$\binom nk=\binom{n-1}{k-1}+\binom{n-1}k,\text{ for }0<k<n,$

which follows from (1 + X)ⁿ = (1 + X)^{n − 1}(1 + X); the leads to the construction of Pascal's triangle.

For determining an individual binomial coefficient, it is more practical to use the formula

$\binom nk = \frac{n^{\underline k}}{k!} = \frac{n(n-1)(n-2)\cdots(n-k+1)}{k(k-1)(k-2)\cdots 1}.$

In this formula the numerator gives the number of k-permutations of n, i.e., of sequences of k distinct elements of S, while the denominator gives the number of such k-permutations that give the same k-combination when the order is ignored.

When k exceeds n/2, the above formula contains factors common to the numerator and the denominator, and canceling them out gives the relation

$\binom nk = \binom n{n-k},\text{ for }0 \le k \le n.$

This expresses a symmetry that is evident from the binomial formula, and can also be understood in terms of k-combinations by taking the complement of such a combination, which is an (n − k)-combination.

Finally there is a formula which exhibits this symmetry directly, and has the merit of being easy to remember:

$\binom nk = \frac{n!}{k!(n-k)!},$

where n! denotes the factorial of n. It is obtained from the previous formula by multiplying denominator and numerator by (n − k)!, so it is certainly inferior as a method of computation to that formula.

The last formula can be understood directly, by considering the n! permutations of all the elements of S. Each such permutation gives a k-combination by selecting its first k elements. There are many duplicate selections: any combined permutation of the first k elements among each other, and of the final (n − k) elements among each other produces the same combination; this explains the division in the formula.

From the above formulas follow relations between adjacent numbers in Pascal's triangle in all three directions:

$\binom nk = \binom n{k-1} \frac {n-k+1}k,\text{ for }k>0$ ,

$\binom nk = \binom {n-1}k \frac n{n-k},\text{ for }{k<n}$ ,

$\binom nk = \binom {n-1}{k-1} \frac nk,\text{ for }n,k>0$ .

Together with the basic cases $\tbinom n0=1=\tbinom nn$ , these allow successive computation of respectively all numbers of combinations from the same set (a row in Pascal's triangle), of k-combinations of sets of growing sizes, and of combinations with a complement of fixed size n − k.

Example of counting combinations

As a concrete example, one can compute the number of five-card hands possible from a standard fifty-two card deck as:

${52 \choose 5} = \frac{52^{\underline5}}{5!} = \frac{52\times51\times50\times49\times48}{5\times4\times3\times2\times1} = \frac{311,875,200}{120} = 2,598,960.$

An alternative, almost equivalent computation, is

${n \choose k} = \frac { ( n - 0 ) }{ (k - 0) } \times \frac { ( n - 1 ) }{ (k - 1) } \times \frac { ( n - 2 ) }{ (k - 2) } \times \frac { ( n - 3 ) }{ (k - 3) } \times \cdots \times \frac { ( n - (k - 1) ) }{ (k - (k - 1)) },$

which gives

${52 \choose 5} = \frac { 52 }{ 5 } \times \frac { 51 }{ 4 } \times \frac { 50 }{ 3 } \times \frac { 49 }{ 2 } \times \frac { 48 }{ 1 } = 2,598,960.$

Using the symmetric formula in terms of factorials gives

$\begin{align} {52 \choose 5} &= \frac{n!}{k!(n-k)!} = \frac{52!}{5!(52-5)!} = \frac{52!}{5!47!} \\ &= \tfrac{80,658,175,170,943,878,571,660,636,856,403,766,975,289,505,440,883,277,824,000,000,000,000}{120\times258,623,241,511,168,180,642,964,355,153,611,979,969,197,632,389,120,000,000,000} \\ &= 2,598,960. \end{align}$

Number of combinations with repetition

A k-combination with repetitions, or k-multicombination, or multiset of size k from a set S is given by a sequence of k not necessarily distinct elements of S, where order is not taken into account: two sequences of which one can be obtained from the other by permuting the terms define the same multiset. If S has n elements, the number of such k-multicombinations is also given by a binomial coefficient, namely by

$\binom{n + k - 1}{k} = \binom{n + k - 1}{n - 1}$

(the case where both n and k are zero is special; the correct value 1 (for the empty 0-multicombination) is given by left hand side $\tbinom{-1}0$ , but not by the right hand side $\tbinom{-1}{-1}$ ).

Example of counting multicombinations

For example, if you have ten types of donuts (n = 10) on a menu to choose from and you want three donuts (k = 3), the number of ways to choose can be calculated as

$\binom{10+3-1}3 = \binom{12}3 = \frac{12\times11\times10}{3\times2\times1} = 220.$

The analogy with the k-combination case can be stressed by writing the binomial coefficient using a rising factorial power

$\binom{n + k - 1}{k} = \frac{n^{\overline k}}{k!} = \frac{n(n+1)\cdots(n+k-1)}{k(k-1)\cdots1}.$

There is an easy way to understand the above result. Label the elements of S with numbers 0, 1, ..., n − 1, and choose a k-combination from the set of numbers { 1, 2, ..., n + k − 1 } (so that there are n − 1 unchosen numbers). Now change this k-combination into a k-multicombination of S by replacing every (chosen) number x in the k-combination by the element of S labeled by the number of unchosen numbers less than x. This is always a number in the range of the labels, and it is easy to see that every k-multicombination of S is obtained for one choice of a k-combination.

A concrete example may be helpful. Suppose there are 4 types of fruits (apple, orange, pear, banana) at a grocery store, and you want to buy 12 pieces of fruit. So n = 4 and k = 12. Use label 0 for apples, 1 for oranges, 2 for pears, and 3 for bananas. A selection of 12 fruits can be translated into a selection of 12 distinct numbers in the range 1,...,15 by selecting as many consecutive numbers starting from 1 as there are apples in the selection, then skip a number, continue choosing as many consecutive numbers as there are oranges selected, again skip a number, then again for pears, skip one again, and finally choose the remaining numbers (as many as there are bananas selected). For instance for 2 apples, 7 oranges, 0 pears and 3 bananas, the numbers chosen will be 1, 2, 4, 5, 6, 7, 8, 9, 10, 13, 14, 15. To recover the fruits, the numbers 1, 2 (not preceded by any unchosen numbers) are replaced by apples, the numbers 4, 5, ..., 10 (preceded by one unchosen number: 3) by oranges, and the numbers 13, 14, 15 (preceded by three unchosen numbers: 3, 11, and 12) by bananas; there are no chosen numbers preceded by exactly 2 unchosen numbers, and therefore no pears in the selection. The total number of possible selections is

$\binom{12+4-1}{12} = \binom{15}{12} = \binom{15}3 = \frac{15\times14\times13}{3\times2\times1} = 455.$

References

External links

C code to generate all combinations of n elements chosen as k
Many Common types of permutation and combination math problems, with detailed solutions
The Unknown Formula For combinations when choices can be repeated and order does NOT matter
[1] Combinations with repetitions (by: Akshatha AG and Smitha B)